
//稀疏数组就是将一个二维数组进行压缩
//实际运用：例如我们可以将一个棋盘(二维数组)进行轻量化储存
public class SparseArray {
    public static void main(String[] args) {
        int Row=10;//棋盘行数
        int Col=10;//棋盘列数
        int [][]chessBoard=new int[Row][Col];

        //放入棋子
        //1代表红方
        //2代表蓝方
        chessBoard[1][2]=1;
        chessBoard[2][3]=2;
        chessBoard[5][5]=55;

        //获取棋盘中有效的数据个数sum
        int sum=0;
        for (int[]chessRow:chessBoard) {
            for (int item:chessRow) {
                if(item!=0){
                    sum++;
                }
            }
        }
        System.out.println("棋盘有效数据："+sum);

        //创建稀疏数组(稀疏数组有三列，但是有sum+1行)
        //其中稀疏数组的特点就是第一行的三个元素分别代表(原棋盘的行，列，有效数据个数(sum))
        int[][]sparseArray=new int[sum+1][3];
        sparseArray[0][0]=Row;//初始化稀疏数组第一行的行数
        sparseArray[0][1]=Col;//初始化稀疏数组第一行的列数
        sparseArray[0][2]=sum;//初始化稀疏数组第一行的棋盘有效数据

        //将棋盘数据存储到稀疏数组中
        int sparseCurrentRow=1;//默认第一行开始存放数据
        for (int i = 0; i < Row; i++) {
            for (int j = 0; j < Col; j++) {
                if(chessBoard[i][j]!=0){
                    sparseArray[sparseCurrentRow][0]=i;
                    sparseArray[sparseCurrentRow][1]=j;
                    sparseArray[sparseCurrentRow][2]=chessBoard[i][j];
                    sparseCurrentRow++;
                }
            }
        }

        System.out.printf("原棋盘：\n");
        for (int i = 0; i < Row; i++) {
            for (int j = 0; j < Col; j++) {
                System.out.printf("%d ",chessBoard[i][j]);
            }
            System.out.println();
        }

        System.out.printf("稀疏数组：\n");
        for (int i = 0; i < sparseArray.length; i++) {
            for (int j = 0; j < sparseArray[i].length; j++) {
                System.out.printf("%d ",sparseArray[i][j]);
            }
            System.out.println();
        }

        System.out.println("=======================");
        System.out.println("稀疏数组复原");
        int[][]chessBoard2=new int[sparseArray[0][0]][sparseArray[0][1]];//实例化原棋盘的大小
        //遍历稀疏数组并将数据复原
        for (int i = 1; i < sparseArray.length; i++) {
            for (int j = 0; j < 3; j++) {
                chessBoard2[sparseArray[i][0]][sparseArray[i][1]]=sparseArray[i][2];
            }
        }

        System.out.printf("复原棋盘：\n");
        for (int i = 0; i < Row; i++) {
            for (int j = 0; j < Col; j++) {
                System.out.printf("%d ",chessBoard2[i][j]);
            }
            System.out.println();
        }
    }
}
